package com.company.tree;

import java.util.LinkedList;
import java.util.Stack;

//https://www.cnblogs.com/0ffff/p/11095250.html
public class TreeSort {

    //---------------二叉树前序遍历------------------------------------------------------------------------------------------------------


    //二叉树先序遍历 根-左-右
    public static void preOrd1(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preOrd1(root.left);
        preOrd1(root.right);
    }


    // Stack是一种后进先出（LIFO）的结构，其继承了Vector的基础上拓展5个方法push()、pop()、peek()、empty()、search()而来
    // 1、push(E):将item推入到栈中
    // 2、pop() :将栈中的最顶一个item推出，并返回被推出的item
    // 3、peek():返回栈中最顶的一个item，但不对其做任何操作
    // 4、empty():判断该栈是否为空
    // 5、search(Object):搜索某一个item在该栈中的位置【位置为离栈顶最近的item与栈顶间距离
    //————————————————
    //版权声明：本文为CSDN博主「陈陈-陈」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
    //原文链接：https://blog.csdn.net/c910511/article/details/79966586
    //PS:虽然Java有提供该类型的数据结构，但是官方推荐使用Deque【
    // 双端队列】，Deque提供更好的完整性和一致性，应该优先使用

    //1个节点1个节点处理, 根节点压栈之后，根的左节点 如果不为空继续压栈、为空则把根节点的右节点继续尝试压栈
    public static void preOrd2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
                System.out.println(node.val);
                stack.push(node);  //压 栈
                node = node.left;
            } else {
                node = stack.pop(); //出栈
                node = node.right;
            }
        }
    }


    //---------------二叉树中序遍历------------------------------------------------------------------------------------------------------

    //左-根-右
    public static void inOrd1(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrd1(root.left);
        System.out.println(root.val);
        inOrd1(root.right);
    }

    //左-根-右
    public static void inOrd2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;   //当前节点
        while (node != null || !stack.empty()) {
            if (node != null) {
                stack.push(node);    //根 压栈
                node = node.left;  //当前节点=根的左节点
            } else {
                node = stack.pop();   //根的左节点为空，则根节点---出栈，当前节点=根
                System.out.println(node.val); //根的值
                node = node.right; //当前节点=根的右节点
            }
        }
    }

    //---------------二叉树 后序遍历------------------------------------------------------------------------------------------------------

    //左-右-根
    public static void postOrd1(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrd1(root.left);
        postOrd1(root.right);
        System.out.println(root.val);
    }

    //非递归方法
    public static void postOrd2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode lastNode = root;
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.peek(); //返回栈中最顶的一个item，但不对其做任何操作

            if (node.right == null || node.right == lastNode) {
                System.out.println(node.val);
                stack.pop();
                lastNode = node;
                node = null;
            } else {
                node = node.right;
            }
        }
    }

    /**
     * 二叉树-层序遍历
     * 从上到下，从左往右，依次遍历
     *
     * 二叉树 每一排的元素 都 从左往右 向list插入 ,然后 LinkedList的元素每打印1个就删除1个
     * @param root
     */
    public static void levelOrdTraversal(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>(); //LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用
        TreeNode node = root;
        if (node == null) {
            return;
        }
        q.offer(node); //添加指定的元素作为这个列表的尾部(最后一个元素)。
        while (!q.isEmpty()) {
            node = q.poll(); //检索并删除列表的头(第一个元素)。
            System.out.println(node.val);
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
    }


    //###############################################################################################
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode n2 = new TreeNode(5);
        TreeNode n3 = new TreeNode(7);

        root.left = n2;
        root.right = n3;


        //    3
        //   /  \
        //  5     7

        //二叉树先序遍历  3 5 7
        //二叉树中序遍历  5 3 7
        //二叉树后序遍历  5 7 3
        System.out.println("用递归实现的 二叉树先序遍历");
        preOrd1(root);

        System.out.println("------------------");
        System.out.println("用 Stack 实现的 二叉树先序遍历");
        preOrd2(root);


        System.out.println("------------------");
        System.out.println("用递归实现的 二叉树 中序遍历");
        inOrd1(root);
        System.out.println("------------------");
        System.out.println("用 Stack 实现的 二叉树 中序遍历");
        inOrd2(root);


        System.out.println("------------------");
        System.out.println("用递归实现的 二叉树 后序遍历");
        postOrd1(root);
        System.out.println("------------------");
        System.out.println("用 Stack 实现的 二叉树 后序遍历");
        postOrd2(root);

        System.out.println("======================");
        System.out.println("用 LinkedList 实现的 二叉树 层序遍历");
        levelOrdTraversal(root);

    }
}
